import java.util.ArrayList;
import java.util.List;

/**
 * @program: LeetCode
 * @description: LeetCode : 763. 划分字母区间
 * @author: WXY
 * @create: 2023-01-24 09:57
 * @Version 1.0
 *
 * 找到每个字符最远的位置，当i 等于这个最远边界了，说明当前的分割结束了
 *
 **/
public class Num763_partitionLabels {
    public List<Integer> partitionLabels(String s) {
        char[] str = s.toCharArray();
        int[] arr = new int[26];
        for (int i = 0; i < s.length(); i++) {
            arr[str[i] - 'a'] = i;
        }
        int left = 0;
        int right = 0;
        ArrayList<Integer> list = new ArrayList<>();
        for (int i = 0; i < str.length; i++) {
            right = Math.max(right, arr[str[i] - 'a']);
            if (i == right) {
                list.add(right - left + 1);
                left = i + 1;
            }
        }
        return list;
    }
}
